{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "f23e0a5b-9cb5-4360-a2e8-2cfccc1c6c5a",
   "metadata": {},
   "source": [
    "# Factors"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 95,
   "id": "e012d79e-9338-4396-bac6-34116cc86bf2",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 4, 5, 10, 20, 25, 50, 100]"
      ]
     },
     "execution_count": 95,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def get_factors(x):\n",
    "    l = []\n",
    "    for i in range(1, x + 1):\n",
    "        if x % i == 0:\n",
    "            l.append(i)\n",
    "    return l\n",
    "\n",
    "get_factors(100)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "34101aa1-cacb-4379-a21e-b6822b6b66fa",
   "metadata": {},
   "source": [
    "# Prime factorization"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "id": "352d39d5-d403-4beb-bee8-e8254f207974",
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    " \n",
    "# A function to print all prime factors of\n",
    "# a given number n\n",
    "def get_prime_factors(n):\n",
    "    l = []\n",
    "    # Print the number of two's that divide n\n",
    "    while n % 2 == 0:\n",
    "        l.append(2)\n",
    "        n = n / 2\n",
    "         \n",
    "    # n must be odd at this point\n",
    "    # so a skip of 2 ( i = i + 2) can be used\n",
    "    for i in range(3,int(math.sqrt(n))+1,2):\n",
    "         \n",
    "        # while i divides n , print i ad divide n\n",
    "        while n % i== 0:\n",
    "            l.append(int(i))\n",
    "            n = n / i\n",
    "             \n",
    "    # Condition if n is a prime\n",
    "    # number greater than 2\n",
    "    if n > 2:\n",
    "        l.append(int(n))\n",
    "        \n",
    "    return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "id": "881e903e-779a-41f0-b2f5-12e8f58218a5",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[3, 3, 5, 7]"
      ]
     },
     "execution_count": 74,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "n = 315\n",
    "get_prime_factors(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "id": "51a6c424-eb86-41c9-a336-1ad3d449c579",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "315"
      ]
     },
     "execution_count": 75,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "3*3*5*7"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "29310c00-acb9-4271-8fe2-802db893a7f9",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "9ccd1f64-8ade-42db-92c3-53d04305f083",
   "metadata": {},
   "source": [
    "# Least common multiple"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "id": "5170f5f8-94f1-44cb-9cfe-d9afeadc0d06",
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import Counter\n",
    "\n",
    "def get_least_common_multiple(a, b):\n",
    "    a,b = list(sorted([a,b]))\n",
    "    \n",
    "    a_prime_factors = get_prime_factors(a)\n",
    "    b_prime_factors = get_prime_factors(b)\n",
    "    \n",
    "    a_counter = Counter(a_prime_factors)\n",
    "    b_counter = Counter(b_prime_factors)\n",
    "\n",
    "    print(a_counter, b_counter)\n",
    "    \n",
    "    for num in a_counter.copy():\n",
    "        if num in b_counter:\n",
    "            if a_counter[num] > b_counter[num]:\n",
    "                b_counter[num] = a_counter[num]\n",
    "            del a_counter[num]\n",
    "    \n",
    "    print(a_counter, b_counter)\n",
    "    \n",
    "    the_factor_list = []\n",
    "    for item in b_counter.items():\n",
    "        the_factor_list += [item[0]] * item[1]\n",
    "    for item in a_counter.items():\n",
    "        the_factor_list += [item[0]] * item[1]\n",
    "    \n",
    "    print(the_factor_list)\n",
    "    \n",
    "    result = 1\n",
    "    for factor in the_factor_list:\n",
    "        result *= factor\n",
    "        \n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "667e9c4e-59c9-4681-932a-3ccc36af8eb3",
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import Counter\n",
    "\n",
    "def get_least_common_multiple2(a, b):\n",
    "    a,b = list(sorted([a,b]))\n",
    "    \n",
    "    i = 1\n",
    "    while True:\n",
    "        if (a*i) % b == 0:\n",
    "            return a*i\n",
    "        i += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "6a538596-45e6-4e04-bd93-211e67945d87",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "36"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "get_least_common_multiple2(12, 18)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 85,
   "id": "e48312aa-9651-4011-a16e-3a955ff6eb71",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Counter({5: 1}) Counter({2: 1, 5: 1})\n",
      "Counter() Counter({2: 1, 5: 1})\n",
      "[2, 5]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "10"
      ]
     },
     "execution_count": 85,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "get_least_common_multiple(5, 10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "id": "b9b7eafb-bcd2-4835-89dc-0f1f02dc66fb",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Counter({2: 2, 3: 1}) Counter({3: 2, 2: 1})\n",
      "Counter() Counter({2: 2, 3: 2})\n",
      "[2, 2, 3, 3]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "36"
      ]
     },
     "execution_count": 86,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "get_least_common_multiple(12, 18)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "id": "ebcc940e-fab9-47b5-9d26-4cd62df3c427",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Counter({3: 1}) Counter({2: 1, 5: 1})\n",
      "Counter({3: 1}) Counter({2: 1, 5: 1})\n",
      "[2, 5, 3]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "30"
      ]
     },
     "execution_count": 87,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "get_least_common_multiple(3, 10)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2a9a039d-cce9-4a31-bfec-7b60c1defb6b",
   "metadata": {},
   "source": [
    "# Greatest common factor "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 96,
   "id": "b804e1dc-dc09-4989-bd18-6d463aa5a5a5",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{1, 2, 5, 10, 50, 25}\n",
      "{1, 2, 4, 5, 100, 10, 50, 20, 25}\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "50"
      ]
     },
     "execution_count": 96,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def get_greatest_common_factor(a, b):\n",
    "    a_prime_factors = set(get_factors(a))\n",
    "    b_prime_factors = set(get_factors(b))\n",
    "    print(a_prime_factors)\n",
    "    print(b_prime_factors)\n",
    "    l = list(a_prime_factors & b_prime_factors)\n",
    "    l.sort()\n",
    "    return l[-1]\n",
    "\n",
    "get_greatest_common_factor(50, 100)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 97,
   "id": "96cf3f80-616f-4fa6-a353-098afd12f0b8",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{1, 3, 21, 7}\n",
      "{1, 2, 3, 5, 6, 10, 15, 30}\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 97,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "get_greatest_common_factor(21, 30)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ea5905f1-e52f-44fc-adef-9b796dc1f77e",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}